#include<stdio.h>
#include<iostream>
using namespace std;
#define TElemType char


//树的存储结构(常见的3种)


//1.双亲表示法(找双亲容易，找孩子难)： 定义结构数组，存放树的结点，每个结点含两个域，数据域.双亲域 
//结点结构定义如下： 
typedef struct PTNode{
	TElemType data;
	int parent; //双亲位置域 
}PTNode;
//树结构定义如下： 
#define MAX_TREE_SIZE 100
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int r, n; //根结点的位置和结点个数 
}PTree;


//2.孩子链表(找孩子容易，找双亲麻烦):	
//		每个结点的孩子结点排列起来，用单链表存储。n个结点有n个孩子链表(叶子结点的孩子链表为空表) 
//		而n个头指针又组成一个线性表，用顺序表(含n个元素的结构数组)存储 
//孩子结点结构定义如下：
typedef struct CTNode{
	int child;
	struct CTNode *next; 
}*ChildPtr;
//双亲结点结构定义如下：
typedef struct {
	TElemType data;
	ChildPtr firstchild; //孩子链表头指针 
}CTBox; 
//树结构定义如下：
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r; //结点数和根结点的位置 
}CTree; 
//2.2带双亲的孩子链表：在双亲定义结构体内再增加一个int ParentsPos; 存储该双亲结点的双亲结点的下标 


//3.孩子兄弟表示法(又叫二叉树表示法，二叉链表表示法)
//		用二叉链表作为树的存储结构，链表的每个结点的两个指针域分别指向 其第一个孩子结点 和 下一个兄弟节点
typedef struct CSNode{
	TElemType data;
	struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree; 



//树与二叉树的转换 
//将树转化为二叉树进行处理，利用二叉树的算法来实现对树的操作 
//由于树和二叉树都可以用二叉链表作为存储结构，则 以二叉链表作为媒介 可以导出树与二叉树之间的一个对应关系 

//将树转换为二叉树------树变二叉树：兄弟相连留长子 
//1.加线：在兄弟之间加一连线
//2.抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
//3.旋转：以树的根节点为轴心，将整树顺时针转45° 


//将二叉树转换成树-----二叉树变树：左孩右右连双亲，去掉原来右孩线 
//1.加线：若p结点是双亲结点的左孩子，则将p的有孩子，右孩子的右孩子...沿分支找到所有右孩子，都与p的双亲用线连起来
//2.抹线: 抹掉原二叉树中双亲与右孩子之间的连线
//3.调整: 将结点按层次排列，形成树结构 




//森林与二叉树的转化

//森林转换成二叉树(二叉树与多棵树之间的关系)-----森林变二叉树：树变二叉根相连  
//1.将各棵树分别转换成二叉树
//2.将每棵树的根节点用线相连
//3.以第一棵树根节点为二叉树的根，再以根节点为轴心，顺时针旋转，构成二叉树型结构 

//二叉树转换为森林------二叉树变森林：去掉全部右孩线，孤立二叉再还原
//1.抹线：将二叉树中根节点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
//2.还原：将孤立的二叉树还原成树 







//树与森林的遍历

//树的遍历(三种方式)
//1.先根(次序)遍历：若树不空，则先访问根节点，然后依次先根遍历各课子树 
//2.后根(次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点 
//3.按层次遍历：若树不空，则自上而下、自左至右访问树中每个结点 

//森林的遍历 
//将森林看作由三部分构成： 
//		1. 森林中第一棵树的根节点 
//		2. 森林中第一棵树的子树森林 
//		3. 森林中其它树构成的森林  
//1. 先序遍历：若森林不空，则访问部分1,先序遍历部分2,先序遍历部分3  
//				即：依次从左至右对森林中每一棵树进行先根遍历 
//2. 中序遍历：若森林不空，则中序遍历部分2，访问部分1，中序遍历部分3
//				即：依次从左至右对森林中的每一棵树进行后根遍历 

int main(void){
	return 0;
}

